package lt89
/*中
89. 格雷编码
n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
	每个整数都在范围 [0, 2^n - 1] 内（含 0 和 2^n - 1）
	第一个整数是 0
	一个整数在序列中出现 不超过一次
	每对 相邻 整数的二进制表示 恰好一位不同 ，且
	第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数 n ，返回任一有效的 n 位格雷码序列 。
*/
/*
格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

格雷码生成规则：以二进制为0值的格雷码为第零项，
	第一次改变最右边的位元，
	第二次改变右起第一个为1的位元的左边位元，
	第三、四次方法同第一、二次，
	如此反复，即可排列出 n 个位元的格雷码。 

	模拟
	格雷编码的生成过程, G(i) = i ^ (i/2);
*/
func grayCode(n int) []int {
	var l uint = 1 << uint(n)
	out := make([]int, l)   //构建长度为l的数组
	for i:=uint(0);i<l;i++{
		out[i] = int( (i>>1) ^ i)
	}
	return out
}


///对称 复制
// class Solution {
// 	public:
// 		vector<int> grayCode(int n) {
// 			// 00  01  n=2
// 			// 0   1
// 			// 00  01   11  10   n=2     
// 			//  0   1    3   2(不进位)     
// 			// 000  001  011  010   110 111  101  100  n=3 2^(n-1)=4 
// 			//  0    1    3    2    6   7    5    4
			//                     110 = 010翻转
// 			//下一个数组的后一半：对称反转+2的n-1次方
// 			vector<int>ans;
// 			ans.push_back(0);
// 			ans.push_back(1);
// 			if(n == 1)
// 			   return ans;
// 			for(int i = 2;i <= n;i++)
// 				for(int j = ans.size()-1;j >=0 ;j--)
// 					ans.push_back(ans[j]+pow(2,i-1));
// 			return ans;
	
// 		}
// 	};
